import numpy as np
import time
from threading import RLock

NUM = 100000


class Cache:
    def __init__(self, size):
        self.size = size
        self.map = {}
        self.head = _Node()
        self.lock = RLock()

    def __setitem__(self, key, value):
        return self.put(value, key)

    def __getitem__(self, item):
        return self.get(item)

    def __contains__(self, item):
        with self.lock:
            return item in self.map

    def put(self, data, id=None):
        with self.lock:
            if id is None:
                id = hex(int(time.time()) * NUM + np.random.randint(0, NUM))[2:]
            elif id in self.map:
                node = self.map[id]
                node.remove()
            node = _Node(id, data)
            self.map[id] = node
            self.head.append(node)
            num = len(self.map)
            while num > self.size:
                last = self.head.prev
                last.remove()
                del self.map[last.id]
                num -= 1
        return id

    def get(self, id):
        """
        Get the value according to the id. A KeyError is raised if the id is not found or the value is already
        removed from this cache.
        :param id the id
        """
        with self.lock:
            if id in self.map:
                node = self.map[id]
                node.remove()
                self.head.insert(node)
                return node.data
        raise KeyError('id "%s" is not found in the cache.' % id)


class _Node:
    def __init__(self, id=None, data=None):
        self.id = id
        self.data = data
        self.next = self
        self.prev = self

    def remove(self):
        self.prev.next = self.next
        self.next.prev = self.prev

    def insert(self, node):
        self.prev.next = node
        node.prev = self.prev
        node.next = self
        self.prev = node

    def append(self, node):
        self.next.insert(node)


if __name__ == '__main__':
    c = Cache(12)
    ids = [c.put(value) for value in range(20)]
    for value in range(20, 30):
        ids.append(c.put(value))
    for id in ids:
        try:
            print(c.get(id))
        except KeyError:
            print('id "%s" is not found' % id)
